package com.jiang.剑指Offer.动态规划.NC281;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/03/24 20:19
 */


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param target int整型
     * @return int整型
     */
    public int cutRope(int target) {
        //不超过3直接计算
        if (target <= 3)
            return target - 1;
        //dp[i]表示长度为i的绳子可以被剪出来的最大乘积
        int[] dp = new int[target + 1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        dp[4] = 4;
        //遍历后续每一个长度
        for (int i = 5; i <= target; i++)
            //可以被分成两份
            for (int j = 1; j < i; j++)
                //取最大值
                dp[i] = Math.max(dp[i], j * dp[i - j]);
        return dp[target];
    }
}
